package org.example.likou150.circularList;

import java.util.HashMap;
import java.util.Map;

class LRUCache {
    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2); // 容量为2

        cache.put(1, 1);   // 缓存是 {1=1}
        cache.put(2, 2);   // 缓存是 {1=1, 2=2}
        System.out.println(cache.get(1)); // 返回 1，缓存是 {2=2, 1=1}

        cache.put(3, 3);   // 淘汰 key 2，缓存是 {1=1, 3=3}
        System.out.println(cache.get(2)); // 返回 -1 (未找到)

        cache.put(4, 4);   // 淘汰 key 1，缓存是 {3=3, 4=4}
        System.out.println(cache.get(1)); // 返回 -1 (未找到)
        System.out.println(cache.get(3)); // 返回 3
        System.out.println(cache.get(4)); // 返回 4


//        LRUCache cache = new LRUCache(1);  // 容量为1
//        cache.put(2, 1);                   // cache = {2=1}
//        System.out.println(cache.get(2));  // 返回 1
//        cache.put(3, 2);                   // 淘汰 key=2，cache = {3=2}
//        System.out.println(cache.get(2));  // 返回 -1（因为 2 被淘汰了）
//        System.out.println(cache.get(3));  // 返回 2

//        LRUCache cache = new LRUCache(2); // 容量为2
//        cache.put(2, 1);
//        cache.put(1,1);
//        cache.put(2,3);
//        cache.put(4,1);
//        System.out.println(cache.get(1));;
//        System.out.println(cache.get(2));;


//        LRUCache cache = new LRUCache(3); // 容量为3
//
//        cache.put(1, 1);
//        cache.put(2, 2);
//        cache.put(3, 3);
//        cache.put(4, 4);   // 淘汰 key=1，缓存是 {2=2, 3=3, 4=4}
//
//        System.out.println(cache.get(4)); // 返回 4
//        System.out.println(cache.get(3)); // 返回 3
//        System.out.println(cache.get(2)); // 返回 2
//        System.out.println(cache.get(1)); // 返回 -1（已淘汰）
//
//        cache.put(5, 5);   // 淘汰 key=4，缓存是 {3=3, 2=2, 5=5}
//
//        System.out.println(cache.get(1)); // 返回 -1（仍未命中）
//        System.out.println(cache.get(2)); // 返回 2
//        System.out.println(cache.get(3)); // 返回 3
//        System.out.println(cache.get(4)); // 返回 -1（已淘汰）
//        System.out.println(cache.get(5)); // 返回 5
    }

    // 哨兵接节点
    private NodeList head;
    private NodeList tail;
    // 哈希索引
    private Map<Integer, NodeList> map;
    // 阈值
    private int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>(capacity);
        head = new NodeList();
        tail = new NodeList();
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        NodeList nodeList = map.get(key);
        if(nodeList==null){
            return -1;
        }

        // 非头节点才移动位置
        if(head!=nodeList){
            // remove
            remove(nodeList);
            // add
            add(nodeList);
        }

        return nodeList.value;
    }

    public void put(int key, int value) {
        if(map.containsKey(key)){
            NodeList nodeList = map.get(key);
            nodeList.value = value;
            // 非头节点才移动位置
            if(head!=nodeList){
                // remove
                remove(nodeList);
                // add
                add(nodeList);
            }
        }else {
            if(map.size() == capacity){
                // remove tail.pre
                map.remove(tail.pre.key);
                remove(tail.pre);
            }

            NodeList nodeList = new NodeList(key, value);
            // add
            add(nodeList);
            map.put(key, nodeList);
        }
    }

    private void remove(NodeList nodeList){
        nodeList.pre.next = nodeList.next;
        nodeList.next.pre = nodeList.pre;
    }

    private void add(NodeList nodeList){
        nodeList.next = head.next;
        head.next.pre = nodeList;
        head.next = nodeList;
        nodeList.pre = head;
    }


























//    private int capacity;
//    private HashMap<Integer, NodeList> map;
//    private NodeList head;
//    private NodeList tail;
//
//    public LRUCache(int capacity) {
//        this.capacity = capacity;
//        map = new HashMap<>(capacity);
//        head = new NodeList();
//    }
//
//    public int get(int key) {
//        NodeList nodeList = map.get(key);
//        if (nodeList == null) {
//            return -1;
//        }
//        replaceNodeListToHead(nodeList);
//        return nodeList.value;
//    }
//
//    public void put(int key, int value) {
//        NodeList nodeList = map.get(key);
//        if (nodeList != null) {
//            nodeList.value = value;
//            replaceNodeListToHead(nodeList);
//            map.put(key, nodeList);
//        } else {
//            if (capacity == map.size()) {
//                NodeList removeNode = removeTail();
//                map.remove(removeNode.key);
//            }
//            NodeList currentNode = new NodeList(key, value);
//            map.put(key, currentNode);
//            addNewNode(currentNode);
//        }
//    }
//
//    private NodeList removeTail() {
//        NodeList temp = tail;
//        tail = tail.pre;
//        if(tail != null){
//            tail.next = null;
//        }else {
//            head.next = null;
//        }
//        return temp;
//    }
//
//    private void addNewNode(NodeList nodeList){
//        nodeList.next = head.next;
//        head.next = nodeList;
//        nodeList.pre = head;
//        if(nodeList.next != null){
//            nodeList.next.pre = nodeList;
//        }
//        if (map.size() == 1) {
//            tail = nodeList;
//        }
//    }
//
//    private void replaceNodeListToHead(NodeList nodeList) {
//        if(nodeList.pre != head){
//            if (nodeList == tail) {
//                tail = tail.pre;
//                tail.next = null;
//            } else {
//                nodeList.pre.next = nodeList.next;
//                if(nodeList.next!=null){
//                    nodeList.next.pre = nodeList.pre;
//                }
//            }
//
//            nodeList.next = head.next;
//            head.next = nodeList;
//            nodeList.pre = head;
//            if (nodeList.next != null) {
//                nodeList.next.pre = nodeList;
//            }
//        }
//    }
//
    private class NodeList {
        private int key;
        private int value;
        private NodeList pre;
        private NodeList next;

        public NodeList() {

        }

        public NodeList(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
}
